package practise_stack;

import java.util.Stack;

public class isPopOrder {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public static boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int len = pushV.length;
        int index1 = 0;
        int index2 = 0;
        //当全部入栈（pushV遍历完）但是 popV[index2] != stack.peek() 就不符合
        while(true) {
            if(pushV[index1] != popV[index2]) {
                //判断一下栈顶元素是否与 popV 中的元素相同
                if(!stack.isEmpty() && popV[index2] == stack.peek()) {
                    //有元素并且相同就出栈
                    index2++;
                    stack.pop();
                } else {
                    //没有元素或不相同就入栈
                    stack.push(pushV[index1++]);
                }
            } else {
                //相同就不要再压入了，共同后移，跳过该元素
                index2++;
                index1++;
            }
            //表示 pushV 已经遍历完了
            if(len == index1) {
                //如果满足条件就循环出栈
                while(index2 != len && popV[index2] == stack.peek()) {
                    index2++;
                    stack.pop();
                }
                //如果pushV的元素与popV的元素不能一一配对，就不能用下面这行代码
//                while(index2 != len && popV[index2++] == stack.pop());
                break;
            }
        }
        return len == index2;
    }

    public static boolean IsPopOrder2 (int[] pushV, int[] popV) {
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            //先压，再判断
            while(!stack.isEmpty() && popV[j] == stack.peek()) {
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println(IsPopOrder2(new int[]{1,2,3,4,5}, new int[]{4,5,3,2,1}));
    }
}
